package leetcode;

import java.util.Arrays;

public class LeetCode26 {

    public static void main(String[] args) {
        LeetCode26 leetCode26 = new LeetCode26();
        leetCode26.removeDuplicates(new int[]{1, 1, 2});
    }

    //算法超时
    public int removeDuplicates1(int[] nums) {
        int lastIndex = nums.length;
        for (int i = 0; i < lastIndex; i++) {
            System.out.println(Arrays.toString(nums));
            for (int j = i + 1; j < lastIndex; ) {
                if (nums[i] == nums[j]) {
                    for (int k = j; k < lastIndex - 1; k++) {
                        nums[k] = nums[k + 1];
                    }
                    lastIndex--;
                } else
                    j++;
            }
        }
        return lastIndex;
    }

    //排序数组 利用了排序数组
    public int removeDuplicates2(int[] nums) {
        int lastIndex = nums.length, j = 0, tmp = 0;
        for (int i = 0; i < nums.length; i++) {
            j = i + 1;
            while (j < lastIndex && nums[j] == nums[i]) {
                j++;
            }
            if (i + 1 != j) {
                //开始移位
                tmp = i + 1;
                while (j < lastIndex) {
                    nums[tmp++] = nums[j++];
                }
                lastIndex -= (j - tmp);
            }
        }
        return lastIndex;
    }

    //------------------------------------------------------------------

    //快慢指针
    //并不需要移动整个数组 只需要把正确的值赋值给
    //需要保证数组不重复，移动的数组还是重复的
    //慢指针代表当前位置
    //不需要移动所有数组
    public int removeDuplicates(int[] nums) {
        //慢指针 指向当前位置
        int i = 0;
        //快指针
        for (int j = 0; j < nums.length; j++) {
            if (nums[i] != nums[j]) {
                nums[++i] = nums[j];
            }
        }
        return i + 1;
    }
}
